//find the maximum subarray(e.g. the subarray with the max sum) using dynamic programming method
#include <iostream>

using std::cout;
using std::endl;

int max_suba(int *a,int len,int &low,int &high) {
	int l = 0;
	int h = 0;
	int max_sum = a[l];
	for(int i=0;i<len;i++) {
		if(a[i]>0) {
			int sum_i = a[i];
			int sum = 0;
			int copy_j = i;
			for(int j = i;j>h;j--) {
				sum += a[j];
				if(sum>sum_i) {
					sum_i = sum;
					copy_j = j;
				}
			}
			if(sum_i>max_sum && copy_j>h+1) {
				max_sum = sum_i;
				l = copy_j;
				h = i;
			}
			else if(sum>0) {
				h = i;
				max_sum += sum;
			}
		}
	}
	
	low = l;
	high = h;
	return max_sum;
}

int main() {
	int a[16] ={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
	int low = 0;
	int high = 0;
	int sum = max_suba(a,16,low,high);
	cout << "max sum= " << sum <<endl;
	cout << "low= " << low << endl;
	cout << "high=" << high << endl;
	return 0;
}